class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(),1);
        vector<int> count(nums.size(),1);
        int res = 1;
        
        for(int j = 1;j < nums.size();j++){
            for(int i = 0;i < j;i++){
                if(nums[i] < nums[j]){
                    if(dp[i] + 1 > dp[j]){
                        count[j] = count[i];
                    }else if(dp[i] + 1 == dp[j]){
                        count[j] += count[i];
                    }
                    dp[j] = max(dp[i] + 1,dp[j]);
                    res = max(res,dp[j]);
                }
            }
        }
        int ret = 0;
        for(int i = 0;i < nums.size();i++){
            if(res == dp[i]){
                ret += count[i];
            }
        }
        return ret;
    }
};
